package cn.genmer.test.security.algorithm.sort;

import java.util.Arrays;

/**
 * @program: java8stream
 * @description: 从数列中挑出一个元素（最前 or 最后），称为 "基准"（pivot）,本类使用最后;
 *
 * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 *
 * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
 * @author: Genmer
 * @create: 2021-07-06 19:45
 **/
public class QuickSort {
    public static void main(String[] args) {
        int[] array = {2, 4, 1, 0, 1};
        System.out.println(String.format("排序前： %s", Arrays.toString(array)));
        sort1(array, 0, array.length-1);
        System.out.println(String.format("排序后： %s", Arrays.toString(array)));
    }

    /**
     * 老的
     * @param array
     * @return
     */
    public static int[] sort(int[] array){
        // 保障原参数不改变
        int[] arr = Arrays.copyOf(array, array.length);
        int[] sorted = quickSort(arr, 0, arr.length - 1);
        return sorted;
    }

    public static int[] quickSort(int[] array, int left, int right){
        // 不先判断， 会StackOverflowError
        if (left < right){
            int parition = parition(array, left, right);
            quickSort(array,left, parition - 1);
            quickSort(array,parition + 1,right);
        }
        return array;
    }

    public static int parition(int[] array, int left, int right){
        // 设置基坐标
        int pivot = left;
        int index = pivot + 1;
        for (int i= index; i<= right; i++){
            if (array[i] < array[pivot]){
                swap(array,i,index);
                index ++;
            }
        }
        swap(array,pivot, index -1);
        return index -1;
    }

    /**
     * 2022.11.24
     */
    public static void sort1(int[] arr, int left, int right){
        if (left >= right) return;

        int mid = partition1(arr, left, right);
        // 排序前： [8, 3, 5, 6, 15, 85, 84, 6, 33, 6]
        // 排序后： [6, 3, 5, 6, 6, 85, 84, 8, 33, 15]
        System.out.println("---------------START--------------------");
        System.out.println(String.format("left -> %s, right -> %s, mid-> %s",left, right, mid));
        sort1(arr, left, mid-1);
        System.out.println(String.format("After Left Sort: %s", Arrays.toString(arr)));
        sort1(arr, mid+1, right);
        System.out.println(String.format("After Right Sort: %s", Arrays.toString(arr)));
        System.out.println("----------------END-----------------");
    }

    /**
     * 存在bug，
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int partition1(int[] arr, int left, int right){

        // 0. 默认右边界作为中轴
        int pivot = right;
        int lp=left;
        int rp = right-1;
        // bug解决方法1
//        while (lp <= rp){
        while (lp < rp){
            while (lp <= rp && arr[lp] <= arr[pivot]) lp++;
            while (lp <= rp && arr[rp] > arr[pivot]) rp--;
            // left还小于right, 就交换各自卡住的那个元素，这样就可以继续遍历，直到双方相等
            if (lp < rp)  swap(arr, lp, rp);
        }
        // bug解决方法2：加入if pivot是中轴坐标， lp应该小于中轴
        if (arr[lp] > arr[pivot])swap(arr, lp, pivot);
//        swap(arr, lp, pivot);
//

        return lp;
    }

    /**
     * 复写
     * 2022.11.25 通过
     * 2022.12.06 通过
     * 2022.12.31 不通过，第一个mid-1忘了
     * 2022.01.13 通过
     * 2023.03.11 通过
     */
    public static void sortTEST(int[] arr, int leftBound, int rightBound){
        if (leftBound >= rightBound) return;

        int mid = partitionTEST(arr, leftBound, rightBound);

        sortTEST(arr, leftBound, mid-1);
        sortTEST(arr, mid+1, rightBound);
    }

    /**
     * 2022.11.25 1. right--写成 right++，最后的swap，left写错，这次记住
     * 2022.11.30 1. right--写成 right++，最后的swap，left写错，这次记住
     * 2022.12.06 通过
     * 2022.13.31 不通过，第一个mid-1忘了
     * 2022.01.13 通过
     * 2023.03.11 通过
     */
    public static int partitionTEST(int[] arr, int leftBound, int rightBound){
        int pivot = arr[rightBound];
        int left = leftBound;
        int right = rightBound -1;

        while (left <= right){
            while (left <= right && arr[left] <= pivot) left++;
            while (left <= right && arr[right] > pivot) right--;

            if (left<right) swap(arr, left,right);
        }

        swap(arr, left, rightBound);

        return left;
    }

    public static int[] swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        return array;
    }
}
